package leetcode_1100;


public class MaximumSumOfTwoNonOverlappingSubarrays_1031 {
	public static void main(String[] args) {
		MaximumSumOfTwoNonOverlappingSubarrays_1031 test = new MaximumSumOfTwoNonOverlappingSubarrays_1031();
		System.out.println(test.maxSumTwoNoOverlap(new int[] {1,0,3}, 1, 2));
	}
	
	class Help{
		int val;
		int left;
		int right;
		public Help(int val,int left,int right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
	public int maxSumTwoNoOverlap(int[] A, int L, int M) {
        for(int i=1;i<A.length;++i) {
        	A[i] += A[i-1];
        }
        Help[] Larr = new Help[A.length-L+1];
        Help[] Marr = new Help[A.length-M+1];
        int i = 0;
        Larr[0] = new Help(A[L-1],0,L-1);
        for(i=L;i<A.length;++i) {
        	Larr[i-L+1] =  new Help(A[i]-A[i-L],i-L+1,i);
        }
        i = 0;
        Marr[0] = new Help(A[M-1],0,M-1);
        for(i=M;i<A.length;++i) {
        	Marr[i-M+1] =  new Help(A[i]-A[i-M],i-M+1,i);
        }
//        Arrays.sort(Larr,(o1,o2)->o2.val-o1.val);
//        Arrays.sort(Marr,(o1,o2)->o2.val-o1.val);
        int res = Integer.MIN_VALUE;
        for(i=0;i<Larr.length;++i) {
        	for(int j=0;j<Marr.length;++j) {
        		if(!judge(Larr[i],Marr[j])) continue;
        		res = Math.max(Larr[i].val+Marr[j].val,res);
        	}
        }
        return res;
        
    }
	
	public boolean judge(Help h1,Help h2) {
		if(h1.right < h2.left || h1.left > h2.right) return true;
		return false;
	}
}
